Матч 46, Сбор пищи (FoodCollecting)

Вам необходимо собрать neededFood единиц еды для солдат. Изначально имеется n работников. Каждый работник за один раунд собирает одну единицу еды. После каждого раунда Вы можете за еду нанимать новых работников. Каждый новый работник стоит price единиц еды. Необходимо вычислить наименьшее число раундов, за которое Вы соберете как минимум neededFood единиц еды.

Класс: FoodCollecting

Метод: int gather(int neededFood, int n, int price)

Ограничения: 1 £ neededFood, n, price £ 1000.

Вход. Количество еды neededFood, которое требуется собрать, изначальное число работников n и цена найма работника price.

Выход. Наименьшее число раундов, за которое можно собрать как минимум neededFood единиц еды.

Пример входа

neededFood	n	price
10	2	1
22	4	1
60	5	6

Пример выхода

4

4

11

РЕШЕНИЕ

жадный алгоритм

Поскольку количество собираемой еды neededFood не более 1000, то нам всегда будет достаточно не более neededFood работников. Предположим, что мы закончим сбор еды имея n + x работников (0 £ n + x £ neededFood). Тогда работников следует набирать как можно быстрее, то есть вся собираемая еда в начальные раунды идет на найм. Когда мы наймем n + x работников, то далее только они будут собирать еду все оставшиеся раунды. Перебираем все допустимые значения x, для каждого из них находим наименьшее количество раундов, за которое будут собраны neededFood единиц еды. Параллельно подсчитываем минимальное значение среди всех найденных значений раундов для каждого x.

ПРОГРАММА

#include <stdio.h>

class FoodCollecting

{

public:

int gather(int neededFood, int n, int price)

{

int EWorkers, workers, food, days, best = 2000000000;

if (n >= neededFood) return 1;

for(EWorkers = n; EWorkers <= neededFood; EWorkers++)

{

food = days = 0; workers = n;

while(food < neededFood)

{

food += workers;

while((workers < EWorkers) && (food >= price))

workers++, food -= price;

days++;

}

if (days < best) best = days;

}

return best;

}

};